package com.nowcoder.code.hjnc;

public class NC32 {

    public int sqrt(int x) {
        int start = 0;
        int end = x;
        int c = 1;
        while (start <= end) {
            c = (start + end) >> 1;
            long pow = (long) c * c;
            long pow1 = pow + (c << 1) + 1;
            if (pow == x || (pow < x && pow1 > x)) {
                return c;
            } else if (pow < x) {
                start = c + 1;
            } else {
                end = c - 1;
            }
        }
        return c;

    }

    public static void main(String[] args) {
        System.out.println(new NC32().sqrt(1518991037));
    }

}
